/*********************************************************/
/* Aluno: Luciano G. S. Ramalho                          */
/* Numero USP: 1002101                                   */
/* MAC122 (BCC) -- 2007                                  */
/* Lista de Exercicios 1 - Listas Ligadas                */
/* Professor: Carlos Eduardo Ferreira                    */
/* Compilador: gcc version 4.1.2 (Ubuntu 4.1.2-0ubuntu4) */
/*********************************************************/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define DEBUG 0
#define TRUE 1
#define FALSE 0
#define ILIMITADO -1

typedef struct no {
    int info;
    struct no* prox;
} celula;

typedef celula* apontador;

int lerArg(int argc, char* argv[], char* argStr[], int ultArgStr);
int lerLista(apontador *inicio);
int lerListaLimitada(apontador *inicio, int tamanho);
void exibirLista(apontador inicio);

/*************************************************************** Questao 1 */

void removerRepetidos(apontador item)
{
    apontador anterior = NULL;
    while (NULL!=item) {
        if ((NULL!=anterior) && (anterior->info == item->info)) {
            anterior->prox = item->prox;
            free(item);
            item = anterior->prox;
        } else {
            anterior = item;
            item = item->prox;
        }
    }
}

int teste_removerRepetidos()
{
    int res;
    apontador inicio = NULL;
    res = lerLista(&inicio);
    if (res < 0)
        return res; /* falha */
    removerRepetidos(inicio);
    exibirLista(inicio);
    putchar('\n');
    return EXIT_SUCCESS;
}

/************************************************************** Questao 2a */

int ocorre(int x, apontador item)
{
    while (NULL!=item) {
        if (item->info == x)
            return TRUE;
        item = item->prox;
    }
    return FALSE;
}

int teste_ocorre()
{
    int res;
    int dado;
    apontador inicio;
    inicio = NULL;
    res = scanf("%d", &dado);
    if (res != 1) {
        printf("teste_ocorre: falha na leitura do dado\n");
        return EXIT_FAILURE;
    }
    res = lerLista(&inicio);
    if (res < 0)
        return res; /* falha */
    printf("%d\n", ocorre(dado,inicio));
    return EXIT_SUCCESS;
}

/************************************************************** Questao 2b */

int adicionar(int dado, apontador *inicio)
{
    apontador novo, item;
    novo = (apontador)malloc(sizeof(celula));
    if (NULL==novo) {
        printf("adicionar: malloc falhou\n");
        return EXIT_FAILURE;
    }
    novo->info = dado;
    novo->prox = NULL;
    if (NULL==*inicio)  /* se a lista estava vazia... */
        *inicio = novo; /* seu inicio agora � o novo item */
    else { /* do contrario, percorrer at� o �ltimo */
        item = *inicio;
        while (NULL!=item->prox)
            item = item->prox; /* o pr�x. do antigo �ltimo agora � o novo */    
        item->prox = novo;
    }
    return EXIT_SUCCESS;
}

int teste_adicionar()
{
    int res;
    int dado;
    apontador inicio;
    inicio = NULL;
    res = scanf("%d", &dado);
    if (res != 1) {
        printf("teste_adicionar: falha na leitura do dado\n");
        return EXIT_FAILURE;
    }
    res = lerLista(&inicio);
    if (res < 0)
        return res; /* falha */
    adicionar(dado,&inicio);
    exibirLista(inicio);
    putchar('\n');
    return EXIT_SUCCESS;
}

/************************************************************** Questao 2c */

void exibirLista(apontador inicio)
{
    apontador item;
    putchar('[');
    item = inicio;
    while (NULL!=item) {
        printf("%d", item->info);
        if (NULL!=item->prox)
            putchar(' '); /*espaco para separar itens*/
        item = item->prox;
    }
    putchar(']');
}

int teste_exibir()
{
    int res;
    apontador inicio = NULL;
    res = lerLista(&inicio);
    if (res >= 0)
        printf("%d itens lidos\n", res);
    else
        return res;
    exibirLista(inicio);
    putchar('\n');
    return EXIT_SUCCESS;
}

/*************************************************************** Questao 3 */

apontador elementoCentral(apontador item)
{
    apontador rapido = item;
    while (NULL!=rapido) {
        if (NULL!=(rapido->prox))
            rapido = (rapido->prox)->prox;
        else
            rapido = NULL;
        if (NULL!=rapido)
            item = item->prox;
    }
    return item;
}

int teste_elementoCentral()
{
    int res;
    apontador centro;
    apontador inicio = NULL;
    res = lerLista(&inicio);
    if (res < 0)
        return res; /* falha */
    centro = elementoCentral(inicio);
    if (NULL!=centro)
        printf("%d\n",centro->info);
    else
        printf("NULL\n");
    return EXIT_SUCCESS;
}

/*************************************************************** Questao 5 */

void inverter(apontador *inicio)
{
    apontador item = *inicio;
    apontador ant, prox;
    ant = NULL;
    while (NULL!=item) {
        prox = item->prox;
        item->prox = ant;
        ant = item;
        item = prox;
    }
    *inicio = ant;
    return;
}

int teste_inverter()
{
    int res;
    apontador inicio = NULL;
    res = lerLista(&inicio);
    if (res < 0)
        return res; /* falha */
    inverter(&inicio);
    exibirLista(inicio);
    putchar('\n');
    return EXIT_SUCCESS;
}

/*************************************************************** Questao 6 */

/* duas implementacoes testadas ok */

void intercalar0(apontador *inicio, apontador lista1, apontador lista2)
{
    apontador item1 = lista1;
    apontador item2 = lista2;
    apontador ult, menor;
        
    if ((NULL==item2) ||
        ((NULL!=item1) && (item1->info < item2->info))) {
        menor = item1;
        if (NULL!=item1)
            item1 = item1->prox;
    } else {
        menor = item2;
        if (NULL!=item2)
            item2 = item2->prox;
    }
    *inicio = menor;
    ult = menor;
    while (NULL!=menor) {
        if ((NULL==item2) ||
            ((NULL!=item1) && (item1->info < item2->info))) {
            menor = item1;
            if (NULL!=item1)
                item1 = item1->prox;
        } else {
            menor = item2;
            if (NULL!=item2)
                item2 = item2->prox;
        }
        ult->prox = menor;
        ult = menor;
    }
}

void intercalar(apontador *inicio, apontador lista1, apontador lista2)
{
    apontador item1 = lista1;
    apontador item2 = lista2;
    apontador ult, menor;
    if ((NULL!=item1) && (NULL!=item2))
        *inicio = (item1->info < item2->info) ? item1 : item2;
    else 
        *inicio = (NULL!=item1) ? item1 : item2;
    if (NULL!=*inicio) {
        if (*inicio == item1) 
            item1 = item1->prox;
        else
            item2 = item2->prox;
    }
    ult = *inicio;
    while (NULL!=ult) {
        if ((NULL!=item1) && (NULL!=item2))
            menor = (item1->info < item2->info) ? item1 : item2;
        else 
            menor = (NULL!=item1) ? item1 : item2;
        if (NULL!=menor) {
            if (menor == item1) 
                item1 = item1->prox;
            else
                item2 = item2->prox;
        }
        ult->prox = menor;
        ult = menor;
    }
}

int teste_intercalar()
{
    int res, tamanho;
    apontador inicio = NULL;
    apontador lista1 = NULL;
    apontador lista2 = NULL;
    res = scanf("%d", &tamanho);
    if (res != 1) {
        printf("teste_intercalar: falha na leitura do tamanho\n");
        return EXIT_FAILURE;
    }
    res = lerListaLimitada(&lista1, tamanho);
    if (res < 0)
        return res; /* falha */
    res = lerLista(&lista2);
    if (res < 0)
        return res; /* falha */
/*
    printf("lista1: ");
    exibirLista(lista1);
    printf("\nlista2: ");
    exibirLista(lista2);
    putchar('\n');
*/
    intercalar(&inicio, lista1, lista2);
    exibirLista(inicio);
    putchar('\n');
    return EXIT_SUCCESS;
}

/*************************************************************** Questao 7 */

void separar(apontador inicio, apontador *pares, apontador *impares)
{
    apontador item = inicio;
    apontador ultPar = *pares;
    apontador ultImpar = *impares;
    
    while (NULL!=item) {
        if ((item->info)%2) { /*impar*/
            if (NULL==*impares)
                *impares = item;
            else
                ultImpar->prox = item;
            ultImpar = item;

        } else { /*par*/
            if (NULL==*pares)
                *pares = item;
            else
                ultPar->prox = item;
            ultPar = item;
        }
        item = item->prox;
    }
    if (NULL!=ultImpar)
        ultImpar->prox = NULL;
    if (NULL!=ultPar)
        ultPar->prox = NULL;
}

int teste_separar()
{
    int res;
    apontador inicio = NULL;
    apontador pares = NULL;
    apontador impares = NULL;
    res = lerLista(&inicio);
    if (res < 0)
        return res; /* falha */
    separar(inicio, &pares, &impares);
    printf("pares:   ");
    exibirLista(pares);
    putchar('\n');
    printf("impares: ");
    exibirLista(impares);
    putchar('\n');
    return EXIT_SUCCESS;
}

/******************************************************************** main */

int main(int argc, char* argv[]) {
    int res, op;
    enum questoes    {q1, q2a, q2b, q2c, q3, q5, q6, q7};
    char* argStr[] = {"1","2a","2b","2c","3","5","6","7"};
    op = lerArg(argc, argv, argStr, q7);
    switch (op) {
        case q1:
            res = teste_removerRepetidos(); break;
        case q2a:
            res = teste_ocorre(); break;
        case q2b:
            res = teste_adicionar(); break;
        case q2c:
            res = teste_exibir(); break;
        case q3:
            res = teste_elementoCentral(); break;
        case q5:
            res = teste_inverter(); break;
        case q6:
            res = teste_intercalar(); break;
        case q7:
            res = teste_separar(); break;
    }
    return EXIT_SUCCESS;
}

/******************************************************** funcoes de apoio */

int lerArg(int argc, char* argv[], char* argStr[], int ultArgStr)
{
    int i;
    if (2==argc) {
        for (i=0; i<=ultArgStr; ++i)
            if (0==strcmp(argv[1],argStr[i]))
                break;
        if (i<=ultArgStr) 
            return i;
    }
    printf("Modo de usar:\n");
    printf("\t$ %s <questao>\n",argv[0]);
    printf("onde <questao> e' uma das seguintes opcoes:\n\t");
    for (i=0; i<=ultArgStr; ++i)
        printf("%s ",argStr[i]);
    putchar('\n');
    return -1;
}

int lerLista(apontador *inicio)
{
    return lerListaLimitada(inicio, ILIMITADO);
}

int lerListaLimitada(apontador *inicio, int tamanho)
{
    int lidos, info;
    apontador novo, anterior;
    lidos = 0;
    anterior = NULL;
    *inicio = NULL;
    while (((ILIMITADO==tamanho) || (lidos < tamanho))
           && (EOF!=scanf("%d",&info))) {
        novo = (apontador)malloc(sizeof(celula));
        if (NULL==novo) {
            printf("lerlista: malloc falhou\n");
            return EXIT_FAILURE;
        }
        novo->info = info;
        if (NULL==anterior)
            *inicio = novo;
        else
            anterior->prox = novo;
        anterior = novo;
        ++lidos;
    }
    return lidos;
}
